package leetcode71_80;

import org.junit.Test;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;

/**
 * @author shhjiang_001
 * @create 2020-06-23 18:47
 */

        /*
        给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。
        示例:
        输入: n = 4, k = 2
        输出:
        [
        [2,4],
        [3,4],
        [2,3],
        [1,2],
        [1,3],
        [1,4],
        ]
        */
public class Solution77 {
    ArrayList<List<Integer>> resLists = new ArrayList<>();
    public List<List<Integer>> combine(int n, int k) {
        ArrayList<Integer> list = new ArrayList<>();
        ArrayDeque<Integer> deque = new ArrayDeque<>();
        int pos = 0;
        method(n,/*pos,*/deque,k);
        return resLists;
    }

    private void method(int ints, /*int pos,*/ ArrayDeque<Integer> deque, int k) {
        if (deque.size() == k){
            resLists.add(new ArrayList<>(deque));
            return;
        }
        for (int i = 1; i <= ints; i++) {
            if (deque.isEmpty() || i > deque.peek() ){
                deque.push(i);
                method(ints,/*pos+1,*/deque,k);
                deque.pop();
            }
        }

    }


    @Test
    public void test(){
        combine(4,3);
    }
}
